/*
 * @lc app=leetcode.cn id=121 lang=java
 *
 * [121] 买卖股票的最佳时机
 */

// @lc code=start
class Solution {
    public int maxProfit(int[] prices) {

        //Solution 1
        /*
        if (prices.length == 0) return 0;

        int lowPrice = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
           lowPrice = lowPrice > prices[i] ? prices[i]: lowPrice;
           maxProfit = Math.max(prices[i] - lowPrice, maxProfit);
        }

        return maxProfit;
        */

        //Solution 2
        if (prices.length == 0) return 0;

        int[] diff = new int[prices.length -1];

        for (int i = 0; i < prices.length - 1; i++) {
            diff[i] = prices[i + 1] - prices[i];
        }

        int[] dp = new int[diff.length + 1];

        int maxProfit = 0;

        for (int i = 1; i< dp.length; i++) {
            dp[i] = Math.max(0, dp[i -1] + diff[i -1]);
            maxProfit = Math.max(maxProfit, dp[i]);
        }

        return maxProfit;
    }
}
// @lc code=end

